package com.clstu.leetcode;

/**
 * leetCode 1653
 */
class Solution9 {

    public static void main(String[] args) {
        System.out.println(minimumDelettions2("bbbbbbbaabbbbbaaabbbabbbbaabbbbbbaabbaaabaabbbaaa" +
                "abaaababbbabbabbaaaabbbabbbbbaabbababbbaaaaaababaaababaabbabbbaaaabbbbbabbabaaaabbbaba"));
    }

    public int minimumDeletions(String s) {
        //版本1,暴力匹配,超时
        // char[] chars = s.toCharArray();
        // //依次找轴,使轴前面都是a,轴后面都是b,不符合的就删除
        // int minDelete = s.length();
        // for(int mid = 0;mid <= s.length();mid++){
        //     int curDelete = 0;
        //     int l=mid-1;
        //     int r=mid;
        //     //这里中间可以做优化,不用再从头统计一遍
        //     while(l>=0){
        //         if(chars[l] == 'b') curDelete++;
        //         l--;
        //     }
        //     while(r<s.length()){
        //         if(chars[r] == 'a') curDelete++;
        //         r++;
        //     }
        //     //记录最小值
        //     minDelete = curDelete<minDelete?curDelete:minDelete;
        // }
        // return minDelete;

        //版本2,优化版
        return minimumDelettions2(s);
    }

    //第二版,第一版的优化
    public static int minimumDelettions2(String s){
        //依次以每一个间隙作为中间轴,不过这次统计的是左边的b和右边的a(不符合的情况,可以利用上一次统计的结论)
        int leftB = 0;
        int rightA = 0;
        //统计在以最左边为对称轴的情况下右边a出现的次数
        for(int i = 0;i<s.length();i++){
            if(s.charAt(i) == 'a') rightA++;
        }
        int minDelete = rightA+leftB;
        //先判断是否全是A或者全是B
        if(rightA == s.length() || rightA==0) return 0;
        for(int mid=0;mid<s.length();mid++){
            if(s.charAt(mid) == 'b'){
                leftB++;
            }else{
                rightA--;
            }
            if(leftB+rightA < minDelete) minDelete=leftB+rightA;
        }
        return minDelete;
    }

}
